#ifndef __LINKED_LIST_H
#define __LINKED_LIST_H

#include <iostream>

using namespace std;

template <class T> class Node;

template <class T> 
class LinkedList
{
public:

   LinkedList();

   ~LinkedList();

   bool empty() const;
   int size() const; 

   void push_back(const T& x);

   T& pop_front();

   void erase(T& item); 
   void printList();

protected:
   Node<T>* p_Head;
   
   int m_Size;
};


template <class T> 
class Node 
{
private:
   Node(const T& x);

   T value;     
   Node<T>* next_link;

   friend class LinkedList<T>;

};





template <class T>
LinkedList<T>::LinkedList(void) : p_Head(0),  m_Size(0)
{

}

template <class T>
LinkedList<T>::~LinkedList(void)
{
	Node<T>* first = p_Head;

    while (first != 0)
    {
		Node<T>* next = first->next_link;
			delete first;
		first = next;
    }
}

template <class T>
bool LinkedList<T>::empty() const
{
	return (m_Size == 0) ? true : false;
}

template <class T>
int LinkedList<T>::size() const
{
	return m_Size;
}

template <class T>
void LinkedList<T>::push_back(const T& x)
{
	Node<T>* newNode = new Node<T>(x);

	Node<T>* p_List = p_Head;
	Node<T>* last = p_Head;

	if (p_Head == NULL)
	{
		p_Head = newNode;
		m_Size++;
		return;
	}

    while (p_List != 0)
    {
		if (p_List->next_link == NULL)
		{
			last = p_List;
		}

		p_List = p_List->next_link;
    }

	last->next_link = newNode;
	m_Size++;
	
}

template <class T>
T& LinkedList<T>::pop_front()
{
	T itemPop;
	Node<T>* ptrItemLink;

	if (p_Head != NULL)
	{
		ptrItemLink = p_Head;
		itemPop		= p_Head->value;
		p_Head		= p_Head->next_link;

		delete ptrItemLink;
	}
	m_Size--;

	return itemPop;
}

template <class T>
void LinkedList<T>::erase(T& item)
{
	Node<T>* p_Pre = NULL;
	Node<T>* p_Del = NULL;

	if (p_Head->value == item) 
	{
		p_Del = p_Head;
		p_Head = p_Del->next_link;

		delete p_Del;
		m_Size--;

        return;
    }
    
	p_Pre = p_Head;
	p_Del = p_Head->next_link;
    
    while (p_Del != NULL) 
	{
        if (p_Del->value == item) 
		{
            p_Pre->next_link = p_Del->next_link;

            delete p_Del; 
			m_Size--;

            break; 
        }

        p_Pre = p_Del;
        p_Del = p_Del->next_link;
    }

}

template <class T>
void LinkedList<T>::printList()
{
	Node<T>* first = p_Head;

    while (first != 0)
    {
		Node<T>* next = first->next_link;
		cout << first->value << endl;
		first = next;
    }
}

template <class T>
Node<T>::Node(const T& x) : value(x), next_link(0)
{

}


#endif